package de.haw.algorithm;

public class MergeSort {
	public static void mergeSort(int[] a, int left, int right) {
		if (left < right) {
			int mid = (right + left) / 2;
			mergeSort(a, left, mid);
			mergeSort(a, (mid + 1), right);
			merge(a, left, mid, right);
		}
	}

	private static void merge(int[] a, int left, int mid, int right) {
		int[] tmp = new int[(right - left) + 1];
		int tmp_i = 0;
		int i = left;
		int j = mid + 1;
		while ((i <= mid) && (j <= right)) {
			if (a[i] < a[j]) {
				tmp[tmp_i] = a[i];
				i++;
			} else {
				tmp[tmp_i] = a[j];
				j++;
			}
			
			tmp_i++;
		}
		while (i <= mid) {
			tmp[tmp_i] = a[i];
			tmp_i++;
			i++;
		}
		;
		while (j <= right) {
			tmp[tmp_i] = a[j];
			tmp_i++;
			j++;
		}
		;
		tmp_i = 0;
		for (i = left; i <= right; i++) {
			a[i] = tmp[tmp_i];
			tmp_i++;
		}
	}
}
